/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/second-max-of-array
   @Language: C++
   @Datetime: 19-03-31 16:09
   */

// Method 1, traverse twice, Time 282ms
class Solution {
public:
	/**
	 * @param nums: An integer array
	 * @return: The second max number in the array.
	 */
	int secondMax(vector<int> &nums) {
		// write your code here
		int max1id=0, max2=INT_MIN;
		for(int i=0; i<nums.size(); ++i)
			if (nums[i]>nums[max1id]) max1id=i;
		for(int i=0; i<nums.size(); ++i)
			if (max1id!=i) max2=max(max2,nums[i]);
		return max2;
	}
};

//Method 2, traverse once, Time 327ms
class Solution {
public:
	/**
	 * @param nums: An integer array
	 * @return: The second max number in the array.
	 */
	int secondMax(vector<int> &nums) {
		// write your code here
		if(nums.size()<2) return 0;
		int max1=max(nums[0],nums[1]), max2=min(nums[0],nums[1]);
		for(int i=2; i<nums.size(); ++i)
			if (nums[i]>=max1){
				max2=max1;
				max1=nums[i];
			}
			else max2=max(max2,nums[i]);
		return max2;
	}
};
